Error diffusion methods, such as the method described in R. W. Floyd & L. Steinberg, “An Adaptive Algorithm for Spatial Grayscale,” in Proceedings of the Society for Information Display, vol. 17, pp 75-77 (1976) (the “Floyd-Steinberg method”), are often used to convert grayscale images to binary images. Such error diffusion methods typically examine a pixel in an input image, determine whether the intensity for the pixel in the input image exceeds a threshold, and assign either a light or dark binary value to the pixel in an output image based on whether it exceeds the threshold. The difference between the input image pixel intensity and the corresponding pixel intensity in the output image is the error for the pixel. Error diffusion methods assign at least a portion of the error to each of one or more neighboring pixels that have not been previously assigned a pixel intensity for the output image. In this manner, the total pixel intensity is substantially maintained throughout the output image without a substantial loss of resolution. However, individual pixels might be lighter or darker in the resulting image than in the input image.
For example, FIG. 1A depicts grayscale values for neighboring pixels in an input image. Each pixel has a grayscale value within a range. In an computer embodiment having 8-bit color, a low value for the range is “0” and a high value for the range is “255.”
FIG. 1B depicts the resulting light/dark values for the four pixels based on a traditional error diffusion method. In FIG. 1B, the threshold for the light/dark determination is the midpoint of the range (i.e., a grayscale value of 127.5). Since the first pixel has a grayscale value greater than the threshold, the pixel is assigned a value of “1” (e.g., “light” or “white”). The difference between the original grayscale value for the first pixel and the resulting high value is defined to be the error value, E1. In other words, the error is equal to the amount of compensation added to a pixel in order to force it to a “0” or “1” value.
For the second pixel, the error value E1 is subtracted from the original value for the pixel. Since the resulting value is less than the threshold, the second pixel is assigned a value of “0” (e.g., “dark”). The error value, E2, is computed for the second pixel. The process iterates over each subsequent pixel until all pixels are computed. Alternate error diffusion methods might diffuse the calculated error among a plurality of unconverted pixels. For example, a first portion of the error value E1 for the first pixel could be subtracted from the second pixel and a second portion could be subtracted from the third pixel.
Exemplary methods of using error diffusion to generate an output image include the methods described in U.S. Pat. Nos. 5,226,094 and 5,374,997 to Eschbach.
One problem inherent in the Floyd-Steinberg method, its progeny and other current error diffusion methods is that error determinations for pixels are performed serially. For image processing hardware in which intensity information for multiple pixels is received in a single time period, the processing of such pixel intensity information must occur at an increased rate to keep pace with the incoming information. For example, if the initial pixel intensity information is received at a rate of 25 MHz and four pixels are received in a clock cycle, a serial error diffusion method must be performed at a rate of 100 MHz in order to retain all data and to keep up with the information stream. As input clock rates and/or the number of pixels for which information is received in a clock cycle increase, the required error diffusion rates can become excessive or impossible to achieve with current serial methods. This is particularly so when information is transferred in an environment in which trace lengths affect the maximum clock rate. Alternatively, processors that perform the computations at the increased rates might not be cost effective for particular applications.
What is needed is a multi-pixel error diffusion method that enables high-speed error diffusion for parallel intensity information.
A need exists for reducing the cost of performing error diffusion for an image.
A need exists for an error diffusion method that operates at the clock rate at which parallel intensity information is received.
The present disclosure is directed to solving one or more of the above-listed problems.